Data processing for image transmission has used a variety of techniques in the past for reducing the bit rate required for transmission of the data. A number of these techniques have been broadly characterized as image compression, which means that perceptually irrelevant aspects of the image data are removed and the redundancies in the data are reduced by the coding technique in order to reduce the bit rate required. The variety of techniques has multiplied as the requirements for image quality have increased at the same time that the demand for the available channel bandwidth has increased.
One of the techniques for achieving such results is the technique known as image compression using vector quantization, in which blocks or vectors, each representing a group of individual pixels, are independently encoded. This technique has been demonstrated to be effective for achieving moderately low rates in bits per pixel.
To maintain the same quality of transmission and further lower the bit rates, it has been necessary to employ a type of vector quantization that can be characterized as vector quantization with memory. Memory is incorporated into the encoding procedure by using memory of previously encoded blocks in each successive input block. A particular type of this technique known as finite state vector quantization (FSVQ) employs a number of states which summarize key information about previously encoded vectors to select one of a family of so-called codebooks to encode each input vector. An example of such a technique is found in the article entitled "Image Compression Based on Vector Quantization With Finite Memory" by R. Aravind and Allen Gersho in Optical Engineering, Vol. 26, July 1987, pp. 570-580.
The encoder and decoder of such a system have a feedback structure in which the internal states determined by the outputs are fed back and used together with the inputs for encoding and decoding. The goal of such finite state techniques is to maintain the quality of the transmission obtained while achieving the desired low bit rate. If the internal state can accurately represent a small region that contains the input vector to be encoded, finite state vector quantization can achieve the aforesaid goal by using a relatively small time varying set of codebooks.
The above referenced technique and others in the image coding environment have faced two special factors relating to image coding. One is the fact that since the images have two dimensional properties, each pixel block, usually a rectangular pixel block, has more adjacent pixels outside the block than does a one-dimensional sample block as in the voice coding environment, and the other is the fact that most common images have very high adjacent pixel correlation. We refer to the former property as spatial contiguity.
Nevertheless, prior attempts to exploit spatial contiguity have failed to make maximum use of the possibilities for both improving the quality of transmission and the reduction of the bit rate. The above-referenced system of Aravind and Gersho diminishes the effect of spatial contiguity by transforming information about the spatially contiguous pixels into indirect information, such as the existence and the types of intensity discontinuities.
The technique of the above-cited article of Aravind and Gersho looks for the edges of images within each block; but for state codebook blocks which have been chosen as best matching image blocks having such internal edges, no pixel is treated more importantly than any other pixel in such codebook block in matching to subsequent adjacent image blocks which may have a continuation of the image edge. Thus, part of the relevance of spatial contiguity is not brought to bear upon the encoding of the subsequent image block, according to the Aravind and Gersho technique.
It is an object of this invention to improve the performance of such coding techniques in either or both of the respects of transmitted image quality and reduction of the required bit rate for transmission. Moreover, a newly blooming market for economical storage techniques for images for archival, for example, for medical, geophysical, aerial or satellite photography purposes, for electronic shopping or for video teleconferencing, increases the need to push such techniques to the limit and furthermore, to make simplicity of the decoding a primary objective of the system even at the expense of some complication of the encoding techniques.